package 每日一题;

import java.util.Arrays;
import java.util.Comparator;

public class No1723完成所有工作的最短时间 {

    /**
     * 给你一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间。
     * 请你将这些工作分配给 k 位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人。
     * 工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。
     * 请你设计一套最佳的工作分配方案，使工人的 最大工作时间 得以 最小化 。
     * 返回分配方案中尽可能 最小 的 最大工作时间 。
     *
     * 示例 1：
     * 输入：jobs = [3,2,3], k = 3
     * 输出：3
     * 解释：给每位工人分配一项工作，最大工作时间是 3 。
     * 示例 2：
     * 输入：jobs = [1,2,4,7,8], k = 2
     * 输出：11
     * 解释：按下述方式分配工作：
     * 1 号工人：1、2、8（工作时间 = 1 + 2 + 8 = 11）
     * 2 号工人：4、7（工作时间 = 4 + 7 = 11）
     * 最大工作时间是 11 。
     *  
     * 提示：
     * 1 <= k <= jobs.length <= 12
     * 1 <= jobs[i] <= 107
     */

    public int minimumTimeRequired(int[] jobs, int k) {

        /**
         * 1.为什么二分法,比直接暴力法快呢?
         * 2.直接暴力法可以剪枝优化吗?
         *
         * 暴力法是从 sum 开始往下减少,并且每次减少都是当前工人少吃一个工作item,时间复杂度是 n!
         * 暴力法也可以剪枝优化,但它是从深处往回,所以关键的情况二无法进行优化。
         *
         * 不要小看暴力法,当没有什么思路时,可以往暴力法上面去做,做到最后再想一想优化。
         * 以后这种 [选数] 的题,尽量往二分法上面去向;
         */

        int left=Arrays.stream(jobs).max().getAsInt();
        int right=Arrays.stream(jobs).sum();
        int mid;

        int maxIndex=0;
        for (int i = 1; i < jobs.length; i++) {
            if(jobs[i]>jobs[maxIndex]){
                maxIndex=i;
            }
        }

        //大元素放在第一位,对于剪枝情况一,可以更快的剪枝
        int temp=jobs[0];
        jobs[0]=jobs[maxIndex];
        jobs[maxIndex]=temp;

        while (left<right){
            mid=(right-left)/2+left;
            //k名工人的工作时间槽
            int[] work=new int[k];

            boolean flag = dfs(jobs, 0, mid, work);
            if(flag){
                //再缩短点时间
                right=mid;
            }else{
                //扩大时间
                left=mid+1;
            }

        }
        return left;
    }

    //index->当前分配到哪一个工作了
    private boolean dfs(int[] jobs,int index,int maxItem,int[] work) {
        if(index==jobs.length){
            return true;
        }
        //然后开始分配
        for (int i = 0; i < work.length; i++) {
            //每一名工人都可以做当前的工作
            work[i]+=jobs[index];

            if(work[i]>maxItem){
                //当前工人吃不下了,让下一个人吃
                work[i]-=jobs[index];
//                return dfs(jobs, index, maxItem, work);
            }else {

                //当前工人未满,吃的动,继续走
                boolean flag = dfs(jobs, index + 1, maxItem, work);

                if (flag) {
                    //走完了,返回true
                    return true;
                }

                //递归里面的工人失败了,回溯
                work[i] -= jobs[index];
            }
            /**
             * 关键剪枝,情况如下:
             * 1.maxItem太小了,都小于最大的任务元素了,每个工人都吃不下
             * 2.当前工人没有活干,就直接跑到下一位员工了,除去情况一,当前员工没活,那么肯定不是最优解
             */
            if(work[i]==0){
                return false;
            }
        }

        return false;
    }


    /**
     * 暴力搜索法
     */
    private int result=Integer.MAX_VALUE;

    public int minimumTimeRequiredNormal(int[] jobs, int k) {
        //k名工人的工作时间槽
        int[] work=new int[k];
        dfs2(jobs,0,0,work);
        return result;
    }

    //index->当前分配到哪一个工作了
    private void dfs2(int[] jobs,int index,int maxItem,int[] work) {
        if(maxItem>result){
            return;
        }
        if(index==jobs.length){
            result=Math.min(result,maxItem);
            return;
        }
        //然后开始分配
        for (int i = 0; i < work.length; i++) {
            //每一名工人都可以做当前的工作
            work[i]+=jobs[index];
            dfs2(jobs,index+1,Math.max(maxItem,work[i]),work);
            work[i]-=jobs[index];
        }

    }

    public static void main(String[] args) {
        No1723完成所有工作的最短时间 n=new No1723完成所有工作的最短时间();
        int[] arr={1,2,4,7,8};

        int result = n.minimumTimeRequired(arr, 2);
        System.out.println(result);
    }

}
